Modular multiplication and modular exponentiation are important operations in many cryptographic systems. Modular multiplication involves finding a product c=ab and then dividing the product c by a modulus M to find a remainder that is referred to a modular product. The result of modular multiplication of a and b performed modulo-M is generally written as c≡ab mod M. The modular multiplication operation is also used to perform modular exponentiation.
Modular multiplication and exponentiation are used in the Diffie-Hellman and RSA public-key cryptosystems, described in, for example, W. Diffie and M. E. Hellman, “New Directions in Cryptography,” IEEE Trans. on Information Theory, vol. 22, pp. 644-654 (1976), and R. L. Rivest, A. Shamir, and L. Adelman, “A Method for Obtaining Digital Signatures and Public-key Cryptosystems,” Communications of the ACM, vol. 21, pp. 120-126 (1978). Modular multiplication is also used in elliptic key cryptography over the finite field GF(2k) and in discrete exponentiation over GF(2k). These applications are described in Q. K. Koç and T. Acar, “Fast Software Exponentiation in GF(2k),” in T. Lang, J.-M. Muller, and N. Takagi, eds., Proceedings, 13th Symposium on Computer Arithmetic, pp. 225-231 (Asilomar, California, Jul. 6-9, 1997). The manipulation of the very large numbers used in these and other cryptographic systems can require complex systems to obtain satisfactory processing speeds. Accordingly, improved methods and apparatus for modular multiplication and exponentiation are needed.